Solving Problems Using Constraint Logic Programming

Competitive programming problems are designed to be solved by making some observations about the problem and coming up with a clever algorithm based on them. This is further facilitated by limiting the number of programming languages and libraries supported by Topcoder platform: if the problem is a perfect fit for some tool or library that is not supported by the platform, the participant has no choice but to roll up their sleeves and figure out that algorithm.

However, I don’t think I need to persuade anybody that various programming languages and specialized libraries are still very useful - both for the competitions that allow the participants to use arbitrary programming tools and for those (undoubtedly rare) cases when one encounters an algorithmic problem outside of programming contests.

In this post I’ll introduce you to one such language - Picat[1], a logic-based multi-paradigm programming language that makes solving certain kinds of algorithmic problems incredibly easy, - and show you how it works on an example problem from a past SRM.

ThreeColorabilityEasy[2]

In this problem you were given a planar graph of a specific structure - the vertices were the lattice points of a rectangular grid, and the edges were horizontal and vertical edges between adjacent vertices, as well as one of the two diagonals in each square cell. Here is an example of such a graph:

The problem asked you to figure out whether the vertices of this graph could be painted using three colors so that no pair of vertices connected by an edge would be painted the same color.

The expected solutions described in the editorial[3] required you to analyze the problem and either try and color the graph (which yielded a lengthy and error-prone code) or figure out the necessary and sufficient condition of the graph being colorable - each row of the diagonals must either equal the previous row or be its opposite. Neither of these approaches is trivial (you can read more about them in the editorial), as is befitting a problem offered as Division 2 Hard.

Picat Solution

Fortunately for us, this problem is an excellent example of a constraint logic programming task, and is perfectly suited to solving using Picat - with barely any thinking required!

A Picat solution literally takes the problem statement and translates it into a set of variables and constraints that describe a valid graph coloring:

• Colors is a rectangular array of vertex colors; Colors :: 1…3 tells us that each color can take values 1, 2 or 3.

• The three foreach loops set the constraints on colors of vertically, horizontally and diagonally adjacent vertices, respectively.

Once the constraints are established, solve(Colors) looks for the solution that would satisfy them. Under the hood it alternates between constraint propagation (figuring out the domains for the unknown variables based on the constraints and known variables) and search (picking one of the unknown variables and assigning it a value from its domain) until a solution is found or all search space is exhausted.

Below is the full solution code. It assumes that the test case is fed to the program via standard input stream as a sequence of lines describing the direction of the diagonals in the graph. The image above would be described by the following input:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
ZNZN
ZNZZ
NZZN

import cp.

do_case(Lines) =>
  H = len(Lines),
  W = len(Lines[1]),

  Colors = new_array(H + 1, W + 1),
  Colors::1. .3,

  foreach(I in 1..H, J in 1..W + 1)
Colors[I, J] # != Colors[I + 1, J]
end,

foreach(I in 1..H + 1, J in 1..W)
Colors[I, J] # != Colors[I, J + 1]
end,

foreach(I in 1..H, J in 1..W)
if Lines[I, J] == 'N'
then
Colors[I, J] # != Colors[I + 1, J + 1]
else
  Colors[I + 1, J] # != Colors[I, J + 1]
end
end,

if solve(Colors) then
println("Yes")
else
  println("No")
end.

main =>
  Lines = read_file_lines()
  .to_array(),
  do_case(Lines)
  .

The beauty of this solution is that one doesn’t need to think about the intricacies of implementing the search, the pruning of the search space and backtracking from branches that don’t yield a solution - Picat does all the heavy lifting for you! You can also switch the solving mechanism from constraint programming to a different tool, such as SAT solver, by changing the import in the first line while keeping the rest of the code intact. Finally, each solver offers you a variety of options and heuristics to choose from to fine-tune the search process. For this problem constraint programming with default options turned out to work just fine - all test cases, including the largest ones, were solved in under two seconds.

Picat can also answer other related questions with very minor code modifications - for this example, it might not just figure out whether the coloring exists but also return any valid coloring or the valid coloring that satisfies some extra requirements (such as being lexicographically first or coloring the fewest vertices red).

Conclusion

I hope you found this post interesting and educational! If you’re curious to learn more about solving other types of competitive programming problems using Picat, check out the paper[5].

Acknowledgements

I’m grateful to Sergii Dymchenko/kit1980 for his help!

References:

1. Picat programming language

2. ThreeColorabilityEasy problem statement

3. Declaratively solving Google Code Jam problems with Picat